#include<iostream>
using namespace std;
#include<memory>
#include<vector>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // return f1(head);
        // return f2(head);
        return f3(head);
    }
    /**
     * 遍历获取链表长度 将前一半入栈 与后一半比对
     * 时间复杂度:O(N) 空间复杂度:O(N)
     * 执行用时：348 ms, 在所有 C++ 提交中击败了5.02%的用户
     * 内存消耗：120.2 MB, 在所有 C++ 提交中击败了34.95%的用户
    */
    bool f1(ListNode* head) {
        auto tem = head;
        //获取head长度
        int hlen = 0;
        while(tem != nullptr) {
            tem = tem->next;
            hlen++;
        }
        cout << "hlen:" << hlen << endl;
        //将head前一半入栈
        vector<int> v;
        tem = head;
        cout << "vector info:";
        for(int i = 0; i < hlen / 2; i++) {
            cout << tem->val << " ";
            v.push_back(tem->val);
            tem = tem->next;
        }
        cout << endl;
        if(hlen & 1 == 1) {
            //奇数 后移到对称点
            tem = tem->next;
        }
        //后一半与前一半进行比对
        while(tem != nullptr) {
            if(tem->val != v.back()) {
                return false;
            }
            v.pop_back();
            tem = tem->next;
        }
        return true;
    }

    /**
     * 快慢指针+逆序链表
     * 这个代码有问题,逆序后没有纠正过来 会内存泄漏 不合理
     * 太乱了,重写f3,解决这个问题
    */
    bool f2(ListNode* head) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        //prep1 和 cp1 用于反转前半部分指针指向 保证反转时是prep1 -> cp1
        ListNode* prep1 = nullptr; 
        ListNode* cp1 = p1;
        bool isOdd = false;
        while(p2 != nullptr) {
            //记录慢指针
            cp1 = p1;
            // cout << "记录当前慢指针:" << cp1->val << endl;

            //快慢指针前进
            p1 = p1->next;
            p2 = p2->next;
            // cout << "前进后慢指针:" << p1->val << endl;
            if(p2) {
                p2 = p2->next;
            } else {
                //奇数个节点
                isOdd = true;
                break;
            }

            //将慢指针的下位指针更改为其前指针
            cp1->next = prep1;
            // cout << "更新慢指针前置指针为:" << (prep1 != nullptr ? prep1->val : -1) << endl;
            //更新前指针
            prep1 = cp1;
            // cout << "更新前置指针:" << prep1->val << endl;
            // cout << endl;

            //    cout << "prep1:" << prep1->val << endl;
            //    cout << "cp1:" << cp1->val << endl;
            //    cout << "p1:" << p1->val << endl;
            //    cout << "-------------------" << endl;
        }
        // cout << p1->val << endl;
        // cout << cp1->val << endl;
        // cout << cp1->next->val << endl;

        //此时p1位于对称右边第一个位置处
        if(isOdd) {
            p2 = prep1;
        } else {
            p2 = cp1;
        }
        // cout << "isOdd:" << isOdd << endl;
        // cout << "p1:" << p1->val << endl;
        // cout << "p2:" << p2->val << endl;
        while(p1 != nullptr) {
            if(p1->val != p2->val) {
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }

    //重写快慢指针+逆序
    bool f3(ListNode* head) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        //prep1 和 cp1 用于反转前半部分指针指向 保证反转时是prep1 -> cp1
        ListNode* prep1 = nullptr; 
        ListNode* cp1 = p1;
        //统计节点奇数偶数性质
        bool isOdd = false;

        //快慢指针前移
        while(p2 != nullptr) {
            //快慢指针前进
            p1 = p1->next;

            p2 = p2->next;
            if(p2) {
                p2 = p2->next;
            } else {
                //奇数个节点
                isOdd = true;
            }

            //将慢指针的下位指针更改为其前指针
            cp1->next = prep1;
            //更新前指针
            prep1 = cp1;
            //记录慢指针 在p1指针后移之后更改其指向
            cp1 = p1;
        }
        
        ListNode* p2next = nullptr;
        ListNode* p2cur = nullptr;
        //此时p1位于对称轴右边第一个位置处
        if(isOdd) {
            p2 = prep1->next;
            //将对称轴的链表再次反转
            prep1->next = cp1;
            p2next = prep1;
        } else {
            p2 = prep1;
            p2next = cp1;
        }
        
        bool ret = true;
        while(p1 != nullptr && ret) {
            if(p1->val != p2->val) {
                ret = false;
            }
            p2cur = p2;

            p1 = p1->next;
            p2 = p2->next;
            //重新反转
            p2cur->next = p2next;
            p2next = p2cur;
        }
        return ret;
    }

    void test() {
        cout << "test" << endl;
        auto head = initList();
        auto tem = head;
        while(tem != nullptr) {
            cout << tem->val << " ";
            tem = tem->next;
        }
        cout << endl;
        printList(head);
        bool ret = isPalindrome(head);
        cout << "ret:" << ret << endl;
        printList(head);
        freeList(&head);
    }

    ListNode* initList() {
        //这个地方内存泄漏了
        ListNode* head = new ListNode();
        ListNode* tem = head;

        vector<int> v = {1,2,2,1};
        for(auto it = v.begin(); it != v.end(); it++) {
            //使用头插法
            // cout << "add:" << *it << endl;
            ListNode* cur = new ListNode(*it);
            tem->next = cur;
            tem = tem->next;
        }
        tem = head->next;
        delete head;
        return tem;
    }

    //需要修改头指针 使用二级指针
    void freeList(ListNode** head) {
        //头指针也销毁
        ListNode* p = (*head);
        ListNode* q;
        while(p) {
            q = p->next;
            delete p;
            p = q;
        }
    }

    int getNodeVal(ListNode* node) {
        if(node) {
            return node->val;
        }
        return -1;
    }

    void printList(ListNode* node) {
        int i = 0;
        while(node && (i++) < 5) {
            cout << node->val << " ";
            node = node->next;
        }
        cout << endl;
    }
};

int main() {
    Solution().test();
    return 0;
}